#include <iostream>
#include <vector>

using namespace std;

class Solution{
public:
    bool stoneGame(vector<int> &piles){
        int size = piles.size();
        vector<vector<int>> dp(size, vector<int>(size, 0));

        for(int i = 0; i < size; i++){
            dp[i][i] = piles[i];
        }

        for(int i = size - 2; i >= 0; i--){
            for(int j = i + 1; j < size; j++){
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }

        return dp[0][size-1] > 0;
    }
};

class Solution{
public:
    bool stoneGame(vector<int> &piles){
        int size = piles.size();
        vector<int> dp(size, 0);
        for(int i = 0; i < size; i++){
            dp[i] = piles[i];
        }

        for(int i = size - 2; i >= 0; i--){
            for(int j = i + 1; j < size; j++){
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j-1]);
            }
        }

        return dp[0] > 0;
    }
};